The memory part of a processor is a significant contributor to the failure rate of a computer. Error correcting codes such as the Hamming codes along with some techniques like the sparing, deallocation or the invert and retry techniques have been implemented to improve the mean time between failure MTBF to an acceptable level. However the demand for machines of better quality offering non disruptive service for longer period of times forces the designer to consider more powerful code than the simple Hamming codes used up to now.
Bose Chaudri Hocquenghem BCH codes are based on the GALOIS field theory. A Galois field is a finite collection of binary elements generated from an irreducible polynomial. A list of irreducible polynomials can be found in the book "Error Correcting Codes" by Peterson and Weldon, the MIT press, Second Edition 1972, for instance.
For the sake of illustration, FIG. 1 represents a (2.sup.4 -1)=15-element Galois field obtained from a specific irreducible generator polynomial of degree 4, represented as the binary expression 10011.
Each element (with i being an integer comprised between 0 and 14) of the field is obtained from .varies..sup.1, for example .varies..sup.2 =.varies..sup.1 x.varies..sup.1, .varies..sup.3 =.varies..sup.2 x.varies..sup.1, etc, where the multiplications are performed modulo the polynomial generator.
.varies..sup.15 =is equal to .varies..sup.0 =0001 which is the identity element of the multiplication.
Two types of operations can be performed within this Galois field: a multiplication modulo 15 (the number of non null element of the field) and an addition modulo 2 (bit by bit). The result of the addition or multiplication of two elements belongs to the field. The rule for the multiplication is shown in FIG. 1. The multiplication by the identity element returns to the same value while the addition of an element of the field to itself gives the null element.
FIG. 2 shows the addition table for this particular Galois field. The null element 0000 for the addition is noted 0. The operations are commutative.
The standard BCH H matrix that would normally be built on above Galois Field is shown in FIG. 3. It is a (15,6) Double Error Correction, triple Error Detection DEC-TED code. It is only shown here for illustration, there is no practical application for this, since 9 check bits would have to be added to protect only 6 data bits. Using irreducible polynomials of degree 5 and 6 would permit to build respectively a (31, 20) and a (63,50) type of code. The latter would fit a full word memory interface for instance. Thirteen check bits would have to be added to the 32 data bits to get a depopulated (45,32) code. Each element in the third row is obtained by raising the corresponding element in the second row at a power 3. because of the rule stated above i.e. the multiplications are done modulo 15, .varies..sup.30 =.varies..sup.0, .varies..sup.33 =.varies..sup.3, 36=.varies..sup.6, .varies..sup.39 =.varies..sup.9, .varies..sup.42 =.varies..sup.12, the third row of the matrix is made of only five elements of the Galois Field and the sequence .varies..sup.0, .varies..sup.3, .varies..sup.6, and repeats itself three times to fit the 15 column matrix. The first row is an all 1 row. It is added to enhance the code to the detection of all triple errors, otherwise there will be no way to make a difference between a double and a triple error.
Using this matrix to check data needs complex decoding circuitry to achieve the correction of up to two errors and the detection of three errors aligned in the same word and thus the error correction and detection operations impair the performance of the overall system incorporating such a data checking means.